package dp;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class CaiYao {

    /*
    * 辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。
    * 医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，
    * 这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，
    * 在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
      如果你是辰辰，你能完成这个任务吗？

输入描述:
第一行有两个整数T（1<=T<=1000）和M（1<=M<=100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出描述:
包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
    * */
    public static void main(String[] args) throws IOException {
        /*BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=0;
        int num=0;
        int[] useTime = new int[num];
        int[] value = new int[num];
        while (br.ready()){
            String[] strs = br.readLine().split(" ");
            T = Integer.parseInt(strs[0]);
            num = Integer.parseInt(strs[1]);
            useTime = new int[num];
            value = new int[num];
            for (int a=0;a<num;a++){
                String[] str1 = br.readLine().split(" ");
                useTime[a] = Integer.parseInt(str1[0]);
                value[a] = Integer.parseInt(str1[1]);
            }
        }
*/

        int[] value = {1,3,4,8,9,1};
        int[] useTime = {2,1,3,4,3,8};
        int res = f1(10,useTime,value);
        System.out.print(res);
    }

    /*
    * 在index位置的药时，后续所能构成的最大价值
    * */
    public static int getMaxValue(int[] userTime,int[] value,int restTime,int index){
        if (restTime<=0){  //没有足够的剩余时间了
            return 0;
        }
        if (index>userTime.length-1){  //药采完了
            return 0;
        }
        int res1= getMaxValue(userTime,value,restTime,index+1);  //不拿当前的  后续可以获得的最大价值
        int res2 = -1;
        if (userTime[index] <= restTime){
            res2 = value[index] + getMaxValue(userTime,value,restTime-userTime[index],index+1);   //拿当前的  可以获得的最大价值
        }
        return Math.max(res1,res2);
    }


    //改动态规划  t:总共的时间  ts花费的时间的数组   vs：可获得价值的数组
    private static int f1(int t, int[] ts, int[] vs) {

        int[][] dp = new int[t+1][ts.length+1]; //dp[i][j]:剩下i时间，j位置及其之后的可以自由选择，返回的最大的价值

        for(int j = ts.length-1; j>=0; j--) {
            for(int i = 1; i <=t; i++) {
                int p1 = dp[i][j+1];
                int p2 = 0;
                if(i>=ts[j]) {
                    p2 = vs[j] + dp[i-ts[j]][j+1];
                }
                dp[i][j] = Math.max(p1, p2);
            }
        }
        for (int x= 0;x<dp.length;x++){
            for (int y = 0;y<dp[x].length;y++){
                System.out.print(dp[x][y]+" ");
            }
            System.out.println(" ");
        }
        return dp[t][0];
    }
}
